package io.github.handyang.algorithms.search;

import java.util.ArrayList;
import java.util.List;

public class OrderSearchST<K, V> implements SymbolTable<K, V> {
    private Node<K, V> head;

    private Node<K, V> tail;

    private int size;

    public OrderSearchST() {
        clear();
    }

    @Override
    public void put(K key, V value) {
        assert key != null;

        Node<K, V> node = findNode(key);
        if (node != null) {
            node.value = value;
        } else {
            Node<K, V> newNode = new Node<>(key, value);
            tail.next = newNode;
            newNode.pre = tail;
            tail = newNode;
            this.size++;
        }
    }


    @Override
    public void delete(K key) {
        assert key != null;

        Node<K, V> node = findNode(key);
        if (node == null) return;

        Node<K, V> pre = node.pre;
        Node<K, V> next = node.next;

        pre.next = next;
        next.pre = pre;

        node.next = null;
        node.pre = null;
        this.size--;
    }

    @Override
    public V get(K key) {
        assert key != null;

        Node<K, V> node = findNode(key);
        if (node == null) return null;

        return node.value;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public Iterable<K> keys() {
        List<K> keys = new ArrayList<>(size());
        Node<K, V> cursor = this.head;

        while (cursor != null) {
            if (cursor.key != null) {
                keys.add(cursor.key);
            }
            cursor = cursor.next;
        }

        return keys;
    }

    @Override
    public void clear() {
        this.head = new Node<>(null, null);
        this.tail = this.head;
        this.size = 0;
    }

    private Node<K, V> findNode(K key) {
        Node<K, V> cursor = this.head;

        while (cursor != null) {
            if (cursor.key != null && cursor.key.equals(key)) return cursor;

            cursor = cursor.next;
        }
        return null;
    }

    private static class Node<K, V> {
        private K key;

        private V value;

        private Node<K, V> next;

        private Node<K, V> pre;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}
